Lambda the Ultimate

An Expressive Language of Signatures. Norman Ramsey and Kathleen Fisher and Paul Govereau. ICFP'05.

Our language includes operations for adding, renaming, and removing components; for changing the type associated with a value; for making a manifest type abstract or vice versa; and for combining two interfaces. These operations can express useful relationships among interfaces.

The authors want to help programmers express nontrivial relationships between interfaces, in order to better understand and explain the structure of complex software systems. To meet this goal they introduce new language design, with fairly rich and expressive concrete syntax.

This line of work is related to issues I wrote about. I remember Ramsey implying he is thinking about these issues in one of his web pages, and I waited to see what he would come up with. I guess this is it...

This is an important area, and I am sure there's still a lot to be done.

An interesting look course and reading list.

Hundreds of Impossibility Results for Distributed Computing
This paper is not as sad as its title impies: it surveys what assumptions and resources are necessary to achieve some specific results in distributed computing. Or if you insist on being pessimistic: what results are impossible without certain assumptions and resources.

We survey results from distributed computing that show tasks to be impossible, either outright or within given resource bounds, in various models. The parameters of the models considered include synchrony, fault-tolerance, different communication media, and randomization. The resource bounds refer to time, space and message complexity.
These results are useful in understanding the inherent difficulty of individual problems and in studying the power of different models of distributed computing. There is a strong emphasis in our presentation on explaining the wide variety of techniques that are used to obtain the results described.

Looks to be helpful for a strategic planning of a distributed PL design and implementation.

The Java EE 5 platform introduces a simplified programming model and eliminates much of the boilerplate that earlier releases required. With Java EE 5 technology, XML deployment descriptors -- that is, side files for defining components and specifying deployment instructions -- are now optional. Instead, you enter the information as an annotation directly into a plain old Java object (POJO) without leaving your source editor. Annotations are a new feature, originally introduced in Java 2 Platform, Standard Edition (J2SE) 5.0. They are a form of metadata with a very simple syntax and recognizable because they begin with a leading at sign (@).

Java EE 5 was announced this week. Read the overview for a quick tour of the new features. Click here for some raves.

It is tempting to make a snide remark about the fact the the last couple of items I posted on LtU are about C++, Ada and now Java, but let's not...

In this article, we show how a statically-typed, statically-built, object-oriented language such as Ada can make full use of the notion of dynamic plug-ins. To that end, we build an extensible application and illustrate adding new functionality to it at run-time via plug-ins. Selected new features of Ada 2005 are used in the implementation and are highlighted. In particular, we use the "distinguished receiver" syntax familiar to users of C++ and Java. We also use one of the new "containers" data structures packages. The main program and plug-ins are built with the GNAT Ada 2005 implementation developed by AdaCore.

This brief DDJ article shows how to build "dynamic" plugins in a statically type-checked language, so this is somewhat related to other ongoing threads.

This is also a chance to take a glimpse at the new version of Ada, which I already mentioned a copule of times. It is interesting to see the convergence of programming languages (e.g., Ada will support the distinguished receiver syntax found in CC+, Java and ilk, provide an interface construct as found in Java, and will ship with a standard container library). On the other hand, each language must carry its own past into the future. Comparing the direction taken by the C++ community to the Ada effort can be somewhat enlightening.

A quick overview of the next version of C++ (scheduled for 2009?).

The most interesting language feature is concepts (see previous item).

One of the fundamental goals is to support user-defined and built-in types equally well. This has been a goal of language design for oh so many years now, and we are not there yet. This is a point worth reflecting upon.

Gabriel Dos Reis and Bjarne Stroustrup. Specifying C++ Concepts. POPL06. January 2006.

We discussed work on improving the C++ template facility before. The basic notion in this paper is concepts, a type system for templates, which will increase the expressiveness of template parameters, and improve compile time error messages. Separate compilation is also an important concern.

I am happy to report that Ada is mentioned, which is a good sign. However, I think there's room for a more detailed discussion and comparison. Other LtU readers will be glad to see that Haskell mentioned as well...

Gilad Is Right (Confessions From A Recovering Typoholic)

If you have not seen Gilad Bracha's talk on pluggable and optional type systems or read the corresponding paper, I really urge you to do so (or invite Gilad as the invited talk in your conference or workshop). The thesis of optional and pluggable type systems is that type-systems should be an optional layer on top of an otherwise dynamically typed system in such a way that (a) types cannot change the run-time behavior of the program, and (b) they cannot prevent an otherwise legal program form compiling or executing. In short what Gilad is saying is that you should not depend on static typing. However, we all know that static type-systems are very addictive, like the finest crack from the backstreets of the ghetto, and I will stop beating around the bush and confess "I am Erik, and I am a (recovering) typoholic".

To illustrate the tantalizing power of static typing, take the concept of axis members in Visual Basic 9. In our first design we keyed "late" binding over XML on the static type of the receiver. For example take the following element declaration

Dim Pu As XElement = <Atom AtomicWeight="244">
                       <Name>Plutonium</Name> 
                       <Symbol AtomicNumber="94">Pu</Symbol>
                       <Radioactive>true</Radioactive> 
                     </Atom> 

Since the static type of Pu is XElement, our compiler interprets the member access expression Pu.Symbol as the call Pu.Elements("Symbol") on the underlying XLinq API. While this is rather cute, it is not without problems. First of all, the XElement class itself has quite a lot of members, and the question is who wins when there is an ambiguity like in Pu.Name. Should this mean Pu.Elements("Name") or should it just directly call the underlying Name property of XElement. Even worse, what happens if the static type of the receiver is Object, but its dynamic type is XElement as in CObj(Pu).Symbol. What we should really do is to extend the Visual Basic late binder to understand axis members, which means we now have two levels of possible ambiguity! At this point, we have lost the majority of our users. Keying axis member binding on the static type of the receiver is just too cute, we are really doing some kind of fancy type-based overloading.

Besides the child axis, we have special support for attribute axis, written using an @-sign as in Pu.@AtomicWeight and for the descendant axis, written using three consecutive dots as in Pu...RadioActive. Obviously, for these two there is no ambiguity with normal member access, depending on how you look at it, it is clear from the member name (Pu .@AtomicWeight and Pu . ••RadioActive) or the selector (Pu •@ AtomicWeight and Pu ••• AtomicWeight) what the intention is, independent of the static type of the receiver. There is no danger for ambiguity, and it all works fine for late-binding when the receiver has type object since we can always interpret Pu.@AtomicWeight as Pu.Attributes("AtomicWeight") and then do ordinary member resolution and type-checking on that.

To solve our pain, we recently decided to also introduce special syntax for the child axis and write Pu.<Symbol> instead of Pu.Symbol. Now there is no ambiguity between Pu.Name, which returns the string "Atom", and Pu.<Name> which returns the XElement child node <Name>Plutonium</Name>. For consistency, we also changed the syntax for the descendant axis to be Pu...<RadioActive> instead of Pu...RadioActive.

I hope that you agree that we have masked out the seductive voices of the static typing sirens by providing a syntax that is more beautiful and a semantics that is much simpler than our previous one that relied heavily on static typing. Gilad is right!

Jeremy Gibbons (2006). Fission for Program Comprehension. Submitted for publication.

Fusion is a program transformation that combines adjacent computations, flattening structure and improving efficiency at the cost of clarity. Fission is the same transformation, in reverse: creating structure, ex nihilo. We explore the use of fission for program comprehension, that is, for reconstructing the design of a program from its implementation. We illustrate through rational reconstructions of the designs for three different C programs that count the words in a text file.

The paper works through the examples meticulously and highlights their recursion schemes. The claim is that the three different wordcount programs might all have arisen from the same high-level design, namely the composition length o words.

The more audacious claim is that [i]f one accepts the claim that design patterns in object-oriented programming correspond to recursion patterns in generic functional programming, then this is further support for Johnson’s slogan that ‘patterns document architectures’.

Interval Computations came up in a recent LtU discussion.

Are they a worthy language feature?